/*二叉树的遍历：建立以左右孩子链接结构表示的二叉树，实现二叉树的先
序、中序、后序的递归和非递归方式遍历，分层遍历、统计树的高度等。*/

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;

/* 二叉树的创建 */
BiTNode* createBiTree(int i, char *a, int len) {
    if (i >= len || a[i] == '#') {
        return NULL;
    }

    BiTNode* root = (BiTNode*)malloc(sizeof(BiTNode));
    if (root == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    root->data = a[i];
    root->lchild = createBiTree(2 * i + 1, a, len);
    root->rchild = createBiTree(2 * i + 2, a, len);

    return root;
}

/* 递归遍历 */
// 先序
void Pre(BiTNode *T) {
    if (T == NULL) {
        return;
    }
    printf("%c ", T->data);  // 访问当前节点
    Pre(T->lchild);          // 遍历左子树
    Pre(T->rchild);          // 遍历右子树
}

// 中序
void In(BiTNode *T) {
    if (T == NULL) {
        return;
    }
    In(T->lchild);      // 遍历左子树
    printf("%c ", T->data); // 访问当前节点
    In(T->rchild);      // 遍历右子树
}

// 后序
void Post(BiTNode *T) {
    if (T == NULL) {
        return;
    }
    Post(T->lchild);        // 遍历左子树
    Post(T->rchild);        // 遍历右子树
    printf("%c ", T->data); // 访问当前节点
}

/* 非递归遍历 */
// 定义栈的节点
typedef struct StackNode {
    BiTNode *data;
    struct StackNode *next;
} StackNode, *Stack;

// 创建栈
Stack createStack() {
    Stack S = (Stack)malloc(sizeof(StackNode));
    if (!S) {
        printf("内存分配失败\n");
        exit(1);
    }
    S->next = NULL;
    return S;
}

// 入栈
void push(Stack S, BiTNode *node) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = node;
    newNode->next = S->next;
    S->next = newNode;
}

// 出栈
int pop(Stack S, BiTNode** node) {
    if (S->next == NULL) {
        return 0;
    }
    StackNode *temp = S->next;
    *node = temp->data; // 保存栈顶节点数据
    S->next = temp->next; // 更新栈顶指针
    free(temp);
    return 1;
}

// 判断栈是否为空
int isEmpty(Stack S) {
    return S->next == NULL;
}

// 释放栈
void freeStack(Stack S) {
    StackNode *temp;
    while (S->next != NULL) {
        temp = S->next;
        S->next = temp->next; // 栈顶指针 S->next 更新
        free(temp);
    }
    free(S);
}

// 先序
void PreOrder(BiTNode *T) { // T 是指向二叉树根节点的指针
    if (!T) return;
    Stack S = createStack();
    push(S, T);
    while (!isEmpty(S)) {
        BiTNode *node;
        if (pop(S, &node)) {
            printf("%c ", node->data);
            if (node->rchild) push(S, node->rchild);
            if (node->lchild) push(S, node->lchild);
        }
    }
    freeStack(S); 
}

// 中序
void InOrder(BiTNode *T) {
    if (!T) return;
    Stack S = createStack();
    BiTNode *current = T; // current用来追踪当前遍历的节点，栈用于保存未处理的节点
    while (current || !isEmpty(S)) {
        while (current) {
            push(S, current);
            current = current->lchild; // 更新
        }
        BiTNode *node;
        if (pop(S, &node)) {
            printf("%c ", node->data);
            current = node->rchild;
        }
    }
    freeStack(S); 
}

// 后序
void PostOrder(BiTNode *T) {
    if (!T) return;

    Stack S = createStack(); // 用于存储节点
    Stack reverse = createStack(); // 用于反向存储节点

    push(S, T); // 将根节点入栈

    while (!isEmpty(S)) {
        BiTNode *node;
        if (pop(S, &node)) { // 弹出栈顶节点
            push(reverse, node); // 将弹出的节点存入反向栈
            if (node->lchild) push(S, node->lchild);
            if (node->rchild) push(S, node->rchild);
        }
    }
    
    while (!isEmpty(reverse)) { // 反向栈非空时，输出节点数据
        BiTNode *node;
        if (pop(reverse, &node)) { // 弹出反向栈中的节点
            printf("%c ", node->data);
        }
    }

    freeStack(S);
    freeStack(reverse); 
}

// 释放二叉树内存
void freeBiTree(BiTNode *T) {
    if (T == NULL) {
        return;
    }
    freeBiTree(T->lchild);  
    freeBiTree(T->rchild);  
    free(T); 
}

/* 分层遍历 */
// 定义队列的节点
typedef struct QueueNode {
    BiTNode *data;
    struct QueueNode *next;
} QueueNode, *Queue;

// 创建队列
Queue createQueue() {
    Queue Q = (Queue)malloc(sizeof(QueueNode));
    if (!Q) {
        printf("内存分配失败\n");
        exit(1);
    }
    Q->next = NULL;
    return Q;
}

// 入队
void enqueue(Queue Q, BiTNode *node) {
    QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = node;
    newNode->next = NULL;
    
    QueueNode *temp = Q;
    while (temp->next != NULL) {// 找到队尾
        temp = temp->next;
    } 
    temp->next = newNode; // 插入队尾
}

// 出队
int dequeue(Queue Q, BiTNode **node) {
    if (Q->next == NULL) {
        return 0;
    }

    // 取出队头节点
    QueueNode *temp = Q->next;
    *node = temp->data; // 将队头节点的数据存入 node 指针
    Q->next = temp->next;
    free(temp);
    return 1;
}

// 判断队列是否为空
int isQueueEmpty(Queue Q) {
    return Q->next == NULL;
}

// 释放队列
void freeQueue(Queue Q) {
    QueueNode *temp;
    while (Q->next != NULL) {
        temp = Q->next;
        Q->next = temp->next;
        free(temp);
    }
    free(Q);
}

// 分层遍历 
void levelOrder(BiTNode *T) {
    if (!T) return;
    Queue Q = createQueue();
    enqueue(Q, T);

    while (!isQueueEmpty(Q)) {
        BiTNode *node;
        if (dequeue(Q, &node)) {
            printf("%c ", node->data);  // 打印当前节点的数据
            if (node->lchild) enqueue(Q, node->lchild);
            if (node->rchild) enqueue(Q, node->rchild);
        }
    }
    freeQueue(Q);
}

/* 计算树的高度 */
int getHeight(BiTNode *T) {
    if (T == NULL) {
        return 0;
    }
    int leftHeight = getHeight(T->lchild);  
    int rightHeight = getHeight(T->rchild);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; 
}

int main() {
    printf("请输入二叉树的结点总数: ");
    int n;
    scanf("%d", &n);
    
    // 为字符数组分配空间
    char *a = (char*)malloc(sizeof(char) * n);  

    // 输入二叉树的结点
    printf("请输入二叉树的结点: ");
    getchar(); // 读取之前留下的换行符
    for (int i = 0; i < n; i++) {
        scanf("%c", &a[i]);
    }

    // 创建二叉树
    BiTNode* T = createBiTree(0, a, n);

    // 输出结果
    printf("\n二叉树的先序遍历结果: \n  递归  : ");
    Pre(T);
    printf("\n  非递归: ");
    PreOrder(T);

    printf("\n二叉树的中序遍历结果: \n  递归  : ");
    In(T);
    printf("\n  非递归: ");
    InOrder(T);

    printf("\n二叉树的后序遍历结果: \n  递归  : ");
    Post(T);
    printf("\n  非递归: ");
    PostOrder(T);

    printf("\n\n二叉树的分层遍历结果: ");
    levelOrder(T);

    printf("\n二叉树的高度: %d\n",getHeight(T));


    freeBiTree(T); // 释放二叉树内存
    free(a);  // 释放数组内存

    return 0;
}